/*
 * @Author: szx
 * @Date: 2021-11-23 20:01:02
 * @LastEditTime: 2022-01-16 14:40:15
 * @Description:
 * @FilePath: \leetcode\100-199\139\139.js
 */
/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
// 定义 dp是前i个是否能够成功拆分的
// var wordBreak = function (s, wordDict) {
//     const n = s.length;
//     const wordDictSet = new Set(wordDict);
//     const dp = new Array(n + 1).fill(false);
//     dp[0] = true;
//     for (let i = 1; i <= n; i++) {
//         for (let j = 0; j < i; j++) {
//             if (dp[j] && wordDictSet.has(s.substr(j, i - j))) {
//                 dp[i] = true;
//                 break;
//             }
//         }
//     }
//     return dp[n];
// };

var wordBreak = function (s, wordDict) {
    const n = s.length;
    const set = new Set(wordDict);
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            if (dp[j] && set.has(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n]
};